package leetcode.code0321;

import java.util.Stack;

public class Solution extends Solution321 {

	@Override
	public int[] maxNumber(int[] nums1, int[] nums2, int k) {
		int len1 = nums1.length, len2 = nums2.length;
		int[] help1 = new int[len1], help2 = new int[len2];//
		int p1 = 0, p2 = 0;
		int[] ans = new int[k];
		int ansi = 0;
		this.init(help1, nums1);
		this.init(help2, nums2);
		int total = len1 + len2;
		while (ansi < k) {
			int num = 0;
			if (total - p1 - p2 == k - ansi) {
				break;
			}
			// [8,6,5,9,7,3,4]
			// [8,3,4,3]
			int tmp1 = this.findMax(len1, p1, len2 - p2, ansi, help1, k);
			int tmp2 = this.findMax(len2, p2, len1 - p1, ansi, help2, k);
			if (tmp1 == len1) {
				num = nums2[tmp2];
				p2 = tmp2 + 1;
			} else if (tmp2 == len2) {
				num = nums1[tmp1];
				p1 = tmp1 + 1;
			} else {
				if (nums1[tmp1] > nums2[tmp2]) {
					num = nums1[tmp1];
					p1 = tmp1 + 1;
				} else if (nums1[tmp1] < nums2[tmp2]) {
					num = nums2[tmp2];
					p2 = tmp2 + 1;
				} else {

				}
			}
			ans[ansi++] = num;
		}
		if (ansi < k) {
			this.update(help1, p1, nums1);
			this.update(help2, p2, nums2);
			while (ansi < k) {
				int num = 0;
				if (p1 == len1) {
					num = nums2[p2++];
				} else if (p2 == len2) {
					num = nums1[p1++];
				} else {
					if (nums1[p1] > nums2[p2]) {
						num = nums1[p1++];
					} else if (nums1[p1] < nums2[p2]) {
						num = nums2[p2++];
					} else {
						int tmp1 = p1;
						int tmp2 = p2;
						while (nums1[help1[tmp1]] == nums2[help2[tmp2]]) {
							tmp1 = help1[tmp1];
							tmp2 = help2[tmp2];
						}
						if (nums1[help1[tmp1]] > nums2[help2[tmp2]]) {
							num = nums1[p1++];
						} else {
							num = nums2[p2++];
						}
					}
				}
				ans[ansi++] = num;
			}
		}

		return ans;
	}

	private int findMax(int len, int p1, int avl, int ansi, int[] help, int k) {
		int share = avl >= k - 1 - ansi ? 0 : k - 1 - ansi - avl;
		int range = len - share;// 开区间
		int ans = p1;
		int p = p1;
		while (p < len && help[p] != p && help[p] < range) {
			p = help[p];
			ans = p;
		}
		return ans;
	}

	private void init(int[] help, int[] nums) {
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < nums.length; i++) {
			while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
				int index = stack.pop();
				help[index] = i;
			}
			stack.add(i);
		}
		while (!stack.isEmpty()) {
			int index = stack.pop();
			help[index] = index;
		}
	}

	// help记录i位置后第一个同nums[i]不一样的数
	private void update(int[] help, int p, int[] nums) {
		int len = help.length;
		help[len - 1] = Integer.MIN_VALUE;
		int last = len - 1;
		for (int i = help.length - 2; i >= p; i--) {
			int cur = nums[i];
			if (cur != nums[last]) {
				help[i] = last;
				last = i;
			} else {
				help[i] = help[i - 1];
			}
		}

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug3();
		so.debug1();
		so.debug2();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
